package list;

//提交记得修改类名为Solution
public class MergeSortRecList {
	public static ListNode sortList(ListNode head) {
		if(head==null || head.next==null) {
			return head;
		}
		//快慢指针找终点。
		ListNode fast = head.next.next;
		ListNode slow = head.next;
		ListNode prevSlow = null;
		while(fast != null && fast.next!=null) {
			prevSlow = slow;
			slow = slow.next;
			fast = fast.next.next;
		}
		//断开链表
		prevSlow.next = null;
		
		//递归式地链式归并排序
		head = sortList(head);
		slow = sortList(slow);
		
		//合并两个有序链表
		head = mergeTwoLists(head, slow);
		return head;
	}
	
	public static ListNode mergeTwoLists(ListNode headA, ListNode headB) {
		//借助虚拟头节点，避免讨论
		ListNode dummy = new ListNode(Integer.MIN_VALUE);
		ListNode tail = dummy;
		//和数组归并排序相同的思路。
		while(headA != null && headB!=null){
			if(headA.val <= headB.val) {
				tail.next = headA;
				headA = headA.next;
			}
			else {
				tail.next = headB;
				headB = headB.next;
			}
			tail = tail.next;
		}
		if(headA!=null) {
			tail.next = headA;
		}
		else {
			tail.next = headB;
		}
		//虚拟头节点的后继即真实合并链表的头节点。
		return dummy.next;
	}
}
